package leetcode_core.leetcode_4;

import org.junit.Test;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年11月18日 8:18
 */
public class CanPartition {

    public boolean canPartition(int[] nums) {
        int sum = 0;
        int n = nums.length;
        for (int num : nums) {
            sum += num;
        }
        if(sum %2 !=0){
            return false;
        }
        sum = sum /2;
        boolean[][] dp = new boolean[n+1][sum+1];
        //base-case
        //1.当背包容量为0,就代表恰好把背包装满了
        for(int i = 0 ;i<=n;i++){
            dp[i][0] = true;
        }
        //2.当没有可选择的元素的时候,此时无解
        for(int j = 1;j<=sum;j++){
            dp[0][j] = false;
        }
        //推导状态转移方程
        //选择当前物品 or 不选择当前的物品
        //选不选中当前的物品取决于选中了当前的物品能否使得背包被装满
        for(int i = 1;i<=n;i++){
            for(int j = 1;j <= sum ;j++){
                if(j - nums[i-1] < 0) {//背包的容量不足
                    dp[i][j] = dp[i - 1][j];//只能继承上次的结果
                }else{
                    dp[i][j] = dp[i-1][j] || dp[i-1][j- nums[i]];
                }
            }
        }
        return dp[n][sum];
    }

}
